package com.hdu.other.dp.intervalDp;

import java.util.Arrays;

public class lc486 {
    class Solution {
        public boolean predictTheWinner(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            int len = nums.length;
            int[][] dp = new int[len][len];
            for (int i = 0; i < len; i++) {
                Arrays.fill(dp[i], -1);
            }
            int first = f(nums, 0, len - 1, dp);
            int second = sum - first;
            return first >= second;
        }

        int f(int[] nums, int l, int r, int[][] dp) {
            if (l > r) {
                return 0;
            } else if (l == r) {
                return nums[l];
            } else if (l + 1 == r) {
                return Math.max(nums[l], nums[r]);
            } else if (dp[l][r] != -1) {
                return dp[l][r];
            } else {
                int p1 = nums[l] + Math.min(f(nums, l + 2, r, dp), f(nums, l + 1, r - 1, dp));
                int p2 = nums[r] + Math.min(f(nums, l, r - 2, dp), f(nums, l + 1, r - 1, dp));
                return dp[l][r] = Math.max(p1, p2);
            }
        }
    }
}
